<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,100分)- 支持优先级的队列（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>实现一个支持优先级的队列&#xff0c;高优先级先出队列&#xff1b;同优先级时先进先出。</p> 
<p>如果两个输入数据和优先级都相同&#xff0c;则后一个数据不入队列被丢弃。</p> 
<p>队列存储的数据内容是一个整数。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>一组待存入队列的数据 (包含内容和优先级)</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>队列的数据内容(优先级信息输出时不再体现)</p> 
<p></p> 
<h4>备注</h4> 
<p>不用考虑输入数据不合法的情况&#xff0c;测试数据不超过100个</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">(10,1),(20,1),(30,2),(40,3)</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">40,30,10,20</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>输入样例中&#xff0c;向队列写入了4个数据&#xff0c;每个数据由数据内容和优先级组成。<br /> 输入和输出内容都不含空格。<br /> 数据40的优先级最高&#xff0c;所以最先输出&#xff0c;其次是30;</p> <p>10和20优先级相同&#xff0c;所以按输入顺序输出。</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">(10,1),(10,1),(30,2),(40,3)</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">40,30,10</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>输入样例中&#xff0c;向队列写入了4个数据&#xff0c;每个数据由数据内容和优先级组成。<br /> 输入和输出内容都不含空格。<br /> 数据40的优先级最高&#xff0c;所以最先输出&#xff0c;其次是30;</p> <p>两个10和10构成重复数据&#xff0c;被丢弃一个。</p> </td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题看上去是让我们使用优先队列&#xff0c;但是实际上不是。</p> 
<p>本题在维护优先级的同时&#xff0c;也要维护去重特性。其中较难的功能点是&#xff1a;</p> 
<blockquote> 
 <p>对于相同优先级的&#xff0c;且不重复的任务&#xff0c;维持插入顺序。</p> 
</blockquote> 
<p>这个功能其实就是让我们实现一个&#xff1a;维护了插入顺序的Set集合。</p> 
<ul><li>对于JS而言&#xff0c;其Set本身就是一个维护了插入顺序的去重集合&#xff0c;因此可以直接复用。</li><li>对于Java而言&#xff0c;我们可以复用LinkedHashSet。</li><li>对于Python而言&#xff0c;其set不维护元素插入顺序&#xff0c;因此我们不能复用。为了避免自己实现OrderedSet&#xff0c;我们可以复用Python的object能力&#xff0c;因此Python的object的keys列是维护了插入顺序的去重集合。</li></ul> 
<p></p> 
<p>我的解题思路如下&#xff1a;</p> 
<p>定义一个字典&#xff0c;用于收集相同优先级的数据&#xff0c;即字典的key是优先级&#xff0c;value是一个维护了插入顺序的Set集合。</p> 
<p>收集完后&#xff0c;我们可以取出字典的key列进行降序排序&#xff08;高优先级优先&#xff09;&#xff0c;然后遍历降序后的key列&#xff0c;逐个打印字典对应key下的value内容。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  const tasks &#61; line
    .slice(1, line.length - 1)
    .split(&#34;),(&#34;)
    .map((s) &#61;&gt; s.split(&#34;,&#34;).map(Number));

  console.log(getResult(tasks));
});

function getResult(tasks) {
  const map &#61; new Map();

  for (let [num, priority] of tasks) {
    if (!map.get(priority)) {
      map.set(priority, new Set());
    }

    map.get(priority).add(num);
  }

  const order &#61; [...map.keys()].sort((a, b) &#61;&gt; b - a);

  const ans &#61; [];
  for (let p of order) {
    ans.push(...map.get(p));
  }

  return ans.join(&#34;,&#34;);
}
</code></pre> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String line &#61; sc.nextLine();

    int[][] tasks &#61;
        Arrays.stream(line.substring(1, line.length() - 1).split(&#34;\\),\\(&#34;))
            .map(s -&gt; Arrays.stream(s.split(&#34;,&#34;)).mapToInt(Integer::parseInt).toArray())
            .toArray(int[][]::new);

    System.out.println(getResult(tasks));
  }

  public static String getResult(int[][] tasks) {
    HashMap&lt;Integer, LinkedHashSet&lt;Integer&gt;&gt; map &#61; new HashMap&lt;&gt;();

    for (int[] task : tasks) {
      int num &#61; task[0];
      int priority &#61; task[1];

      map.putIfAbsent(priority, new LinkedHashSet&lt;&gt;());
      map.get(priority).add(num);
    }

    StringJoiner sj &#61; new StringJoiner(&#34;,&#34;);
    map.keySet().stream()
        .sorted((a, b) -&gt; b - a)
        .forEach(
            p -&gt; {
              map.get(p).forEach(num -&gt; sj.add(num &#43; &#34;&#34;));
            });

    return sj.toString();
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
line &#61; input()

tasks &#61; list(map(lambda s: list(map(int, s.split(&#34;,&#34;))), line[1:len(line)-1].split(&#34;),(&#34;)))


# 核心代码
def getResult():
    dic &#61; {}

    for num, priority in tasks:
        dic.setdefault(priority, {})
        dic[priority].setdefault(num, None)

    order &#61; list(dic.keys())
    order.sort(reverse&#61;True)

    ans &#61; []
    for p in order:
        ans.extend(list(dic[p].keys()))

    return &#34;,&#34;.join(map(str, ans))


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>